#include <iostream>
using namespace std;


struct ListNode { 
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) { }
    ListNode(int val) : val(val), next(nullptr) { } 
    ListNode(int val, ListNode* next) : val(val), next(next) { } 
};


class Soultion {
public:

    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* tmp;

        while(cur) {
            tmp = cur->next; // 保存后续节点
            
            cur->next = pre; //反转操作

            pre = cur;       // 更新指针，让pre -> cur, cur -> cur->next
            cur = tmp;
        }

        return pre;
    }

    ListNode* createNode(int val) {
        return (new ListNode(val));
    }

    void printNode(ListNode* head) {
        ListNode* cur = head;
        while(cur) {
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

};


int main(void) {
    Soultion s;
    ListNode* head = s.createNode(1);
    ListNode* node1 = s.createNode(2);
    ListNode* node2 = s.createNode(3);
    ListNode* node3 = s.createNode(4);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;

    s.printNode(head);

    head = s.reverseList(head);
    s.printNode(head);

    return 0;
}


